{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Edit Distance\n",
    "\n",
    "[The Original Question](https://mp.weixin.qq.com/s/W9lXzCl5MD7Qyvwyk5z18A)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question\n",
    "\n",
    "Given two strings, determine the edit distance between them. The edit distance is defined as the minimum number of edits (insertion, deletion, or substitution) needed to change one string to the other."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example\n",
    "\n",
    "`biting` and `sitting` have an edit distance of `2` (substitute `b` for `s`, and insert a `t`)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def edit_distance(string_A: str, string_B: str) -> int:\n",
    "    if string_A == '' and string_B == '':\n",
    "        return 0\n",
    "    elif string_A == '' and string_B != '':\n",
    "        return len(string_B)\n",
    "    elif string_A != '' and string_B == '':\n",
    "        return len(string_A)\n",
    "    elif string_A[0] == string_B[0]:\n",
    "        return edit_distance(string_A[1:], string_B[1:])\n",
    "    else:\n",
    "        dist_A = edit_distance(string_A, string_B[1:])\n",
    "        dist_B = edit_distance(string_A[1:], string_B)\n",
    "        dist_C = edit_distance(string_A[1:], string_B[1:])\n",
    "        return min(dist_A, dist_B, dist_C) + 1\n",
    "    pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n"
     ]
    }
   ],
   "source": [
    "print(edit_distance('biting', 'sitting'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Notes\n",
    "\n",
    "[Calculate the distances between 2 string](https://blog.csdn.net/gplwz_1314/article/details/39181947)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
